package 链表.分隔链表;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2023/8/3 16:47
 * @description:
 * @version:
 */

/**
 * 给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分
 * 这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。
 */
public class Solution2 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1,new ListNode(4,new ListNode(3,new ListNode(2,new ListNode(5,new ListNode(2))))));
        ListNode head2 = new ListNode(22);
        head2.next = head;
        ListNode[] listNodes = splitListToParts(head2, 3);
        System.out.println("lll");
    }

    public static ListNode[] splitListToParts(ListNode head, int k) {
        int[] listLen = new int[k];
        ListNode[] res = new ListNode[k];
        //先遍历获取链表的长度
        int length = 0;
        ListNode p = head;
        while (p != null) {
            length++;
            p = p.next;
        }
        if (length >= k) {
            //单个链表最小长度
            int singleLen = length / k;
            int modNum = length % k;
            for (int i = 0; i < k; i++) {
                if (i < modNum) {
                    listLen[i] = singleLen + 1;
                }else {
                    listLen[i] = singleLen;
                }
            }
        } else {
            int modNum = length % k;
            for (int i = 0; i < k; i++) {
                if (i < modNum) {
                    listLen[i] = 1;
                }
            }
        }
        ListNode q = new ListNode();
        q = head;
        for (int i = 0; i < k; i++) {
            int tmpLen = listLen[i];
            ListNode newHead = null;
            ListNode r = null;
            while (tmpLen > 0) {
                ListNode s = q.next;
                q.next = null;
                if (newHead == null) {
                    newHead = q;
                    r = newHead;
                } else {
                    r.next = q;
                    r = r.next;
                }
                q = s;
                tmpLen--;
            }
            res[i] = newHead;
        }
        return res;
    }

}
